//
// Created by Administrator on 2023/7/28.
//
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <numeric>

using namespace std;

class Solution {
public:
    vector<string> sortPeople(vector<string> &names, vector<int> &heights) {
        // 身高各不相同，则可以用哈希表
        unordered_map<int, string> um;
        int n = names.size();
        for (int i = 0; i < n; ++i) {
            um[heights[i]] = names[i];
        }
        sort(heights.begin(), heights.end(), greater<>());
        vector<string> ans(n);
        for (int i = 0; i < n; ++i) {
            ans[i] = um[heights[i]];
        }
        return ans;
    }
};
class Solution2 {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int x, int y) {
            return heights[x] > heights[y];
        });
        vector<string> res(n);
        for (int i = 0; i < n; i++) {
            res[i] = names[indices[i]];
        }
        return res;
    }
};


int main() {
    vector<string> names{"Mary", "John", "Emma"};
    vector<int> heights{180, 165, 170};
    Solution2 s;
    auto ans = s.sortPeople(names, heights);
    for (auto &x: ans) cout << x << endl;
}